package first

import "strconv"

/*
	输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。
	比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

	示例 1:

	输入: n = 1
	输出: [1,2,3,4,5,6,7,8,9]
	说明：

	用返回一个整数列表来代替打印
	n 为正整数

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func PrintNumbers(n int) []int {
	return printNumbers1(n)
}

func printNumbers(n int) []int {
	// 1. 求出n位最大的10进制数
	num := 1
	for i := 1; i <= n; i++ {
		num *= 10
	}
	res := make([]int, 0)
	// 2. 遍历打印
	for i := 1; i < num; i++ {
		res = append(res, i)
	}
	return res
}

// 要求1~n中所有十进制数实际上就是求n个0-9的全排列、也就是给定一个字符串、长度为n、每一位都从1取到9
// n没有指定范围、所以这里用字符串可以防止越界
func printNumbers1(n int) []int {
	result := make([]int, 0)
	printNumberRecurse(n, "", 0, &result)
	return result[1:]
}

func printNumberRecurse(n int, curs string, index int, result *[]int) {
	if index == n {
		data, _ := strconv.Atoi(curs)
		*result = append(*result, data)
		return
	}
	for i := 0; i <= 9; i++ {
		c := strconv.Itoa(i)
		printNumberRecurse(n, curs+c, index+1, result)
	}
}
